package java111;

import java.util.Arrays;
import java.util.Scanner;

public class Day18 {
    //https://www.nowcoder.com/practice/c43a0d72d29941c1b65c857d8ac9047e
    public String compressString (String param) {
        // write code here
        int count = 0;
        StringBuilder sb = new StringBuilder();
        int left = 0, right = 0;
        while(right < param.length()){
            count = 0;
            sb.append(param.charAt(left));
            while(right < param.length() && param.charAt(right) == param.charAt(left)){
                right++;
                count++;
            }
            if(count > 1){
                sb.append(count);
            }
            left = right;
        }
        return sb.toString();
    }


    //https://ac.nowcoder.com/acm/problem/26221
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int k = in.nextInt();
            Orange[] orange = new Orange[n];
            for(int i = 0; i < n; i++){
                orange[i] = new Orange();
                orange[i].acid = in.nextInt();
            }
            for(int i = 0; i < n; i++){
                orange[i].sweet = in.nextInt();
            }
            Arrays.sort(orange);
            long res1 = 0, res2 = 0;
            int tmp = 0;
            while(tmp < k){
                res1 += orange[tmp].acid;
                res2 += orange[tmp++].sweet;
            }
            System.out.println(res1 + " " + res2);
        }
    }


    //https://www.nowcoder.com/practice/2820ea076d144b30806e72de5e5d4bbf
    public int knapsack (int v, int n, int[][] vw) {
        // dp[i][j] 表示 从前 i 个物品中选择体积不超过 j 的最大价值
        int[][] dp = new int[n+1][v+1];
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < v+1; j++){
                int tmp = vw[i-1][0];
                dp[i][j] = dp[i-1][j];
                if(j - tmp >= 0){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-tmp] + vw[i-1][1]);
                }
            }
        }
        return dp[n][v];
    }
    //https://ac.nowcoder.com/acm/contest/77922/E
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int v = in.nextInt();
        int[] vi = new int[n];
        int[] wi = new int[n];
        for(int i = 0; i < n; i++){
            vi[i] = in.nextInt();
            wi[i] = in.nextInt();
        }
        int[][] dp1 = new int[n+1][v+1];
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < v+1; j++){
                dp1[i][j] = dp1[i-1][j];
                if(j-vi[i-1] >= 0){
                    dp1[i][j] = Math.max(dp1[i][j], dp1[i-1][j-vi[i-1]] + wi[i-1]);
                }
            }
        }
        System.out.println(dp1[n][v]);
        for(int i = 1; i < v+1; i++){
            dp1[0][i] = -1;
        }
        for(int i = 1; i < n+1; i++){
            for(int j = 1; j < v+1; j++){
                dp1[i][j] = dp1[i-1][j];
                if(j-vi[i-1] >= 0 && dp1[i-1][j-vi[i-1]] != -1){
                    dp1[i][j] = Math.max(dp1[i][j], dp1[i-1][j-vi[i-1]] + wi[i-1]);
                }
            }
        }
        System.out.println(dp1[n][v] == -1 ? 0 : dp1[n][v]);
    }
}

class Orange implements Comparable<Orange>{
    public Integer sweet;
    public Integer acid;
    public int compareTo(Orange o1){
        if(o1.sweet == this.sweet){
            return this.acid - o1.acid;
        } else {
            return o1.sweet - this.sweet;
        }
    }
}